(파이썬 S/W 문제해결 기본) Queue - 5097번 5105번 5099번 5102번

5097번 - 회전

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

리스트 내장함수인 pop()과 append()로 쉽게 해결

T = int(input())

for test_case in range(1, T+1): # 입력 길이 N, 회전 수 M
N, M = map(int, input().split())
seq_lst = [num for num in input().split()]

    # M번 반복
    for _ in range(M):
        # 맨 앞 원소를 빼서 pop(), 맨 뒤로 추가 append()
        seq_lst.append(seq_lst.pop(0))

    print('#{} {}'.format(test_case, seq_lst))

---

5105번 - 미로의 거리

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

지난 미로 문제는 DFS, 이번에는 BFS로 해결
DFS는 재귀적으로, BFS는 반복을 통해 접근

def BFS(x, y): # 현재 좌표 등록
path.append((x, y))
visited.append((x, y))

    while path:
        # 경로 맨 앞 원소 제거
        cur_x, cur_y = path.pop(0)

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if (next_x, next_y) not in visited and (0<=next_x<N and 0<=next_y<N) and maze[next_y][next_x] != 1:
                if maze[next_y][next_x] == 3:
                    return path_len[cur_x][cur_y]

                path.append((next_x, next_y))
                visited.append((next_x, next_y))
                path_len[next_x][next_y] = path_len[cur_x][cur_y] + 1

def findStart():
for y in range(N):
for x in range(N):
if maze[y][x] == 2:
return x, y

T = int(input())

for test*case in range(1, T+1): # 미로의 크기
N = int(input())
maze = [[int(num) for num in input()] for * in range(N)]

    # 시작점 찾기
    startX, startY = findStart()

    # 방문체크, 경로 큐, 경로 길이 리스트
    visited, path, path_len = [], [], [[0]*N for _ in range(N)]

    # 시계방향 (우, 하, 좌, 상)
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]

    ans = BFS(startX, startY)
    if ans is None:
        ans = 0

    print('#{} {}'.format(test_case, ans))

---

5099번 - 피자 굽기

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

화덕을 돌려가며 피자를 굽자

def pizza(): # 초기 화덕 큐
oven = [] # 피자 번호
pNum = 0

    # (init) 빈 화덕에 피자 채우기
    for _ in range(N):
        oven.append([C[pNum], pNum])
        pNum += 1

    # (반복) 오븐에 마지막 피자만 남을 때 까지
    while len(oven) != 1:
        # 현재 화덕 확인으로 치즈가 반 녹음
        oven[0][0] = oven[0][0] // 2

        # 치즈가 다 녹았다면
        if oven[0][0] == 0:
            # 꺼내고
            oven.pop(0)
            # 피자가 남았다면
            if pNum != len(C):
                # 화덕에 넣어준다
                oven.append([C[pNum], pNum])
                pNum += 1
        # 덜 녹았으면 회전
        else:
            oven.append(oven.pop(0))

    return oven[0][1] + 1

T = int(input())

for test_case in range(1, T+1): # 화덕의 크기 N, 피자 개수 M
N, M = map(int, input().split()) # 치즈의 양 C
C = [int(amount) for amount in input().split()]

    print('#{} {}'.format(test_case, pizza()))

---

5102번 - 노드의 거리

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

전역변수 ‘ans’를 사용하지 않고 BFS() 함수에서 return path_len[]를 하면 테스트 케이스 중 하나가 오답이 된다
간선이 없는 경우인거 같은데…

def makeGraph():
graph = {key + 1: set() for key in range(V)}

    for _ in range(E):
        key, val = map(int, input().split())
        graph[key].add(val)
        graph[val].add(key)

    return graph

def BFS(s, g):
global ans
path.append(s)
visited[s] = True

    while path:
        node = path.pop(0)

        for next_node in myGraph[node]:
            if not visited[next_node]:
                path.append(next_node)
                visited[next_node] = True
                path_len[next_node] = path_len[node] + 1

                if next_node == g:
                    ans = path_len[next_node]
                    return
    return

T = int(input())

for test_case in range(1, T+1):
V, E = map(int, input().split())
myGraph = makeGraph()
S, G = map(int, input().split())

    path = []
    visited = [False] * (V+1)
    path_len = [0] * (V+1)
    ans = 0
    BFS(S, G)

    print('#{} {}'.format(test_case, ans))

---